package origami;

import origami.Node.*;

/**
 * Graph is very big
 * Limitations:
 * 1. OutOfMemoryError will occur in IterativeMethod (cannot store all guid is a set)
 * 2. StackOverflowError will occur in ColorRecursiveMethod (recursion can get really big)
 *
 * Assumptions:
 * 1. cannot use any distributed HashSet to store the visiting nodes
 * 2. no more than one edge to the same child (single edge from a node to itself is allowed)
 *
 * Motivation:
 * 1. Focus on memory efficiency
 * 2. Add minimum data on each node (only 2 bits for color)
 * 3. cannot use recursion -> implementation will be iterative
 * 4.   In order to keep track on our path we will use both coloring and edge flipping
 *      for every node do the following:
 *          4.a color the node in grey
 *          4.b iterate over its children:
 *              4.b.1:  if he has than two grey children -> we found a loop
 *              4.b.2:  otherwise find the next white child, move to it, and flip the edge
 *                      by removing the child from the parent, and adding the parent as a child (memory stays the same)
 *              4.b.3:  if no white children left -> color it black, move back to the parent (the only grey child),
 *                      and flip the edge to return graph to original condition
 * 5. when the root changes to black, we are done iterating over the tree and return false;
 *
 */
public class MemoryRestrictedMethod implements ICycleRecognition {

    @Override
    public boolean findLoop(Node startNode) {
        if (startNode == null) {
            return false;
        }
        Node currentNode = startNode;
        while (!Color.BLACK.equals(currentNode.getColor())) {
            currentNode.setColor(Color.GREY);
            int greyCounter = 0;
            boolean foundWhite = false;
            Node nextWhite = null;
            Node prevGrey = null;
            for (Node child : currentNode.getChildren()) {
                if (Color.GREY.equals(child.getColor())) {
                    // node that points to itself
                    if (currentNode == child){
                        return true;
                    }
                    // no self edges
                    prevGrey = child;
                    greyCounter++;
                    if (greyCounter >= 2) {
                        //TODO: undo graph edges changes from this point to the top
                        return true;
                    }
                }
                if (!foundWhite && Color.WHITE.equals(child.getColor())) {
                    nextWhite = child;
                    foundWhite = true;
                }
            }
            // no more children to explore
            if (nextWhite == null){
                currentNode.setColor(Color.BLACK);
                // special case for the start node since it has no prevGrey and no flip edge is needed
                if (currentNode != startNode) {
                    flipEdge(currentNode, prevGrey);
                    currentNode = prevGrey;   // has to be no null, the prev parent
                } else {
                    currentNode = startNode;
                }
            }
            // new child to extend to
            else {
                flipEdge(currentNode, nextWhite);
                currentNode = nextWhite;
            }
        }
        return false;
    }

    private void flipEdge(Node nodeA, Node nodeB){
        nodeA.getChildren().remove(nodeB);
        nodeB.getChildren().add(nodeA);
    }
}
